1. Field of the Invention
The present invention relates to automatic speech recognition modules and more specifically to a system and method of decomposing a lattice transition matrix into a block diagonal matrix.
2. Introduction
A lattice is a mathematic structure of a set of data together with one or more relations or operators defined over the set. Lattices may be used to process any type of data. The present invention is disclosed in the context of one of many uses of lattices. In large vocabulary continuous speech recognition (LVCSR), the word search space, which is prohibitively large, is commonly approximated by word lattices. Usually these word lattices are acyclic and have no a-priori structures. Their transitions are weighted by acoustic and language model probabilities. More recently a new class of normalized word lattices has been proposed. These word lattices (a.k.a. sausages) are more efficient than canonic word lattices and they provide an alignment for all the strings in the word lattices. The present invention relates to a general framework for lattice chunking. One way to characterize the present invention is the pivot algorithm or method. In terms of state transition matrix, the present invention corresponds to decomposing the lattice transition matrix into a block diagonal (chunk) matrix.